The present invention relates generally to a residue circuit. More specifically, the invention relates to a residue circuit for calculating a remainder the case where a divisor is 3.
As an example of the conventionally available such type residue circuit, there is a circuit, in which remainders in division of dividends by a divisor of 3 are preliminarily stored employing a read-only-memory (ROM) and the dividends are input as address signal for reading out the preliminarily stored remainders from the ROM.
As alternative example, there is a circuit as illustrated in FIG. 9. The shown circuit includes a data input Di, a load signal LD, a clock C1, a subtrahend counter 27 taking an operation enabling signal E2 as input for outputting a counter value C.sub.out, a divisor counter 28 taking the operation enabling signal E2 as input for outputting a carry Cr.sub.0, and a judgement portion 29 taking the counter value C.sub.out and the carrier Cr.sub.0 as inputs for outputting the operation enabling signal E3.
FIGS. 10A to 10E are timing charts showing operation of the circuit set forth above. Initially, a dividend is loaded in the subtrahend counter 27 by operating the load signal LD. The judgement portion 29 makes judgement of the sizes of the dividend and the divisor of 3 that the operation enabling signal E3 is output when the dividend is greater than or equal to the divisor.
In response to the operation enabling signal E3, the subtrahend counter 27 initiates subtracting operation. In conjunction therewith, the divisor counter 28 performing counting up until the divisor is reached. The judgement portion 29 compares the counter value C.sub.out of the subtrahend counter 27 and the divisor again at the timing where the carry signal Cr.sub.i is input so as to continue further counting when the counter value C.sub.out is greater than or equal to the divisor and, otherwise, to terminate counting by terminating the operation enabling signal E3. Upon termination of the counter operation, the counter value C.sub.out of the subtrahend counter 27 becomes the remainder to be obtained.
In case of the conventional circuit employing the ROM, the ROM having a memory capacity of (number of bits of the divisor .times.2 powered by number of bit of dividends) becomes necessary for each dividend. Therefore, according to increasing of number of dividend to be stored, required memory capacity becomes huge.
On the other hand, in case of the circuit illustrated in FIG. 9, since repeated counting process is performed, it takes a long period to obtain the remainder and thus is not suitable for high speed operation.